package com.lun.easy;

import java.util.LinkedList;

import com.lun.util.BinaryTree.TreeNode;

public class UnivaluedBinaryTree {
	
	//方法一：递归法
    public boolean isUnivalTree(TreeNode root) {
        if(root == null) return true;
        
        if(root.left != null && root.left.val != root.val)
        	return false;
        
        if(root.right != null && root.right.val != root.val)
        	return false;
        
        return isUnivalTree(root.left) && isUnivalTree(root.right);
    }
    
    //方法二：递归法
    public boolean isUnivalTree2(TreeNode root) {
    	LinkedList<TreeNode> stack = new LinkedList<>();
    	stack.push(root);
    	while(!stack.isEmpty()) {
    		TreeNode node = stack.pop();
    		
    		if(node.val != root.val)
    			return false;
    		
            if(node.left != null)
            	stack.push(node.left);
            
            if(node.right != null)
            	stack.push(node.right);
    	}
    	return true;
    }
    
}
